# 思路：每一层的最小深度等于 左子树/右子树 的最小值 +1
from tools.treeNode import Tree


def minDepth(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    min_depth = 10 ** 5
    if root.left:
        min_depth = min(minDepth(root.left), min_depth)
    if root.right:
        min_depth = min(minDepth(root.right), min_depth)
    return min_depth + 1


root = Tree(1)
root.left = Tree(2)
root.right = Tree(2)
root.left.left = Tree(3)
root.left.right = Tree(4)
# root.right.left = Tree(4)
# root.right.right = Tree(3)
print(minDepth(root))  # 3
